package com.cat.dataStructure03;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.Arrays;

/**
*   @description https://leetcode.cn/problems/greatest-common-divisor-traversal/
*   @author 曲大人的喵
*   @create 2025/11/18 15:11
*   @since JDK17
*/

public class Solution84 {
    static int N = ((int) 1e5);
    static int[]lpf = new int[N + 1], f;
    static {
        for (int i = 2; i <= N; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= N; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }
    }
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        f[fx] = fy;
    }
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length, max = Arrays.stream(nums).max().getAsInt();
        f = new int[n + max + 1];
        for (int i = 0; i <= max + n; i++) {    // 初始化
            f[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int x = nums[i], p = lpf[x]; p > 1; x /= p, p = lpf[x]) {
                merge(i, n + p);
            }
        }
        int root = find(0);
        for (int i = 1; i < n; i++) {
            if (find(i) != root) {
                return false;
            }
        }
        return true;
    }
}
